export class HashTable {
    constructor() {
        this.upperTol = 10
        this.lowerTol = 2
        this.initCapacity = 7
        this.capacityIndex = 0

        this.hashCalc = new MyHash()

        this.capacity = [
            53, 97, 193, 389, 769, 1543, 3079, 6151, 12289,
            24593, 49157, 98317, 196613, 393241, 786433,
            1572869, 3145739, 6291469, 12582917, 25165843,
            50331653, 100663319, 201326611, 402653189, 805306457, 1610612741
        ]

        this.M = this.capacity[this.capacityIndex]
        this.size = 0
        this.hashTable = new Array(this.M)

        for (let i = 0; i < this.M; i++) {
            this.hashTable[i] = new Map()
        }
    }

    hash(key) {
        const hash = this.hashCalc.hashCode(key)
        return (hash & 0x7fffffff) % this.M
    }

    getSize() {
        return this.size
    }

    add(key, value) {
        const hash = this.hash(key)
        const map = this.hashTable[hash]

        if (map.has(key))
            map.set(key, value)
        else {
            map.set(key, value)
            this.size++;

            if (this.size >= this.upperTolerance * this.M && this.capacityIndex + 1 < this.capacity.length) {
                this.capacityIndex++
                this.resize(this.capacity[this.capacityIndex])
            }
        }
    }

    remove(key) {
        const hash = this.hash(key)
        const map = this.hashTable[hash]

        let value = null

        if (map.has(key)) {
            value = map.delete(key)
            this.size--

            if (this.size < this.lowerTolerance * this.M && this.capacityIndex > 0) {
                this.capacityIndex--
                this.resize(this.capacity[this.capacityIndex])
            }
        }

        return value
    }

    set(key, value) {
        const hash = this.hash(key)
        const map = this.hashTable[hash]

        if (!map.has(key)) {
            throw new Error(`${key} doesn't exist`)
        }

        map.set(key, value)
    }

    contains(key) {
        return this.hashTable[this.hash(key)].has(key)
    }

    get(key) {
        return this.hashTable[this.hash(key)].get(key)
    }

    resize(newM) {
        const newHashTable = new Array(newM)

        for (var i = 0; i < newM; i++) {
            newHashTable[i] = new Map()

        }

        const oldM = this.M
        this.M = newM

        for (let i = 0; i < oldM; i++) {
            const map = this.hashTable[i]
            const keys = map.getKeys()
            for (const key of keys) {
                newHashTable[this.hash(key)].set(key, map.get(key))
            }
        }

        // 重新设置当前hashTable
        this.hashTable = newHashTable
    }
}

class MyHash {
    constructor() {
        this.store = new Map()
    }

    // 生成hash
    hashCode(key) {
        let hash = this.store.get(key)

        if (hash) { // 如果 这个hash没有进行保存 就生成，并且记录
            hash = this.calcHash2(key)
            this.store.set(key, hash)
        }

        return hash
    }

    // 得到的数字比较小 六七位数 以下  辅助函数：生成hash -
    calcHash1(key) {
        // 生成hash 随机小数 * 当前日期毫秒 * 随机小数
        let hash = Math.random() * Date.now() * Math.random()

        // hash 取小数部分的字符串
        hash = hash.toString().replace(/^\d*\.\d*?([1-9]+)$/, "$1")
        hash = parseInt(hash)

        return hash
    }

    // 得到的数字很大 十几位数 左右  辅助函数：生成hash -
    calcHash2(key) {
        // 生成hash 随机小数 * 当前日期毫秒 * 随机小数
        let hash = Math.random() * Date.now() * Math.random()

        // hash 向下取整
        hash = Math.floor(hash)
        return hash
    }
}